/*
 * EnumerateFiber.java
 *
 * Created on June 28, 2004, 3:25 PM
 */

package com.milowski.monos.binomial;

import java.util.*;
import java.io.*;
import com.milowski.monos.monomial.*;

/**
 *
 * @author  R. Alexander Milowski
 */
public class Fiber {
   
   /** Creates a new instance of EnumerateFiber */
   public Fiber() {
   }
   
   public static MonomialTree enumerate(Monomial u,LexOrderedList basis) {
      
      // Create the monomial tree to store the fiber
      MonomialTree fiber = new MonomialTree(basis.getLexOrder());
      
      // Index the basis initial terms by a monomial tree
      BinomialTree initial = new BinomialTree(basis.getLexOrder());
      
      // Index the basis final terms by a monomial tree
      BinomialTree reverse = new BinomialTree(basis.getLexOrder());
      
      // Load the monomial trees
      Iterator binomials = basis.iterator();
      while (binomials.hasNext()) {
         Binomial toadd = (Binomial)binomials.next();
         initial.addBinomial(toadd,true);
         reverse.addBinomial(toadd,false);
      }
      
      // Normalize the lattice point
      boolean normalized = false;
      short [] tvalues = new short[basis.getLexOrder().size()];
      do {
         // Find a divisor amongst the initial terms
         Iterator divisors = initial.divisors(u);
         if (divisors.hasNext()) {
            // Get the divisor's binomial
            Binomial divisor = (Binomial)divisors.next();
            
            // Calculate the new lattice point
            short [] leadingValues = divisor.getLeadingTerm();
            short [] trailingValues = divisor.getTrailingTerm();
            short [] vvalues = u.getValues();
            for (int i=0; i<tvalues.length; i++) {
               tvalues[i] = (short)(vvalues[i] - leadingValues[i] + trailingValues[i]);
            }
            
            // Add the old monomial to the fiber
            fiber.add(u);
            
            // Create the new monomial
            u = new Monomial(tvalues);
         } else {
            // No divisor, so the point is optimal and the monomial is optimized
            normalized = true;
         }
      } while (!normalized);
      
      // Create the active list
      List active = new ArrayList();
      
      // Add the optimal point to the active list
      active.add(u);
      while (active.size()>0) {
         
         // Get a monomial from the active list
         Monomial v = (Monomial)active.remove(0);
         
         // Add it to the fiber
         fiber.add(v);
         
         // Get a divisor amongst the final terms
         Iterator divisors = reverse.divisors(v);
         if (divisors.hasNext()) {
            
            // Take the first divisor
            Binomial divisor = (Binomial)divisors.next();
            
            // Calculate the next point in the fiber
            short [] leadingValues = divisor.getLeadingTerm();
            short [] trailingValues = divisor.getTrailingTerm();
            short [] vvalues = v.getValues();
            for (int i=0; i<tvalues.length; i++) {
               tvalues[i] = (short)(vvalues[i] - leadingValues[i] + trailingValues[i]);
            }
            // Add it if it isn't in the fiber
            if (!fiber.contains(tvalues)) {
               active.add(new Monomial(tvalues));
            }
         }
      }
      
      // Return the fiber
      return fiber;
      
   }
   
   public static void main(String [] args) {
      if (args.length!=2) {
         System.err.println("Usage: Fiber lattice-point basis-matrix");
         System.exit(1);
      }

      try {
         FileReader input = new FileReader(args[0]);
         BufferedReader breader = new BufferedReader(input);
         String spec = breader.readLine();
         String [] vvalues = spec.split("\\s");
         Monomial v = new Monomial(vvalues.length);
         for (int i=0; i<vvalues.length; i++) {
            v.getValues()[i] = Short.parseShort(vvalues[i]);
         }
         input.close();
         
         input = new FileReader(args[1]);
         LexOrderedList basis = MatrixBasis.readMatrixAsBinomials(input);
         input.close();
         
         if (basis.size()==0 || ((Binomial)basis.get(0)).getLeadingTerm().length!=v.getValues().length) {
            System.err.println(basis.size()==0 ? "Basis is empty!" : "Number of variables does not match in basis and lattice-point.");
            System.exit(1);
         } else {
            MonomialTree fiber = Fiber.enumerate(v, basis);
            Iterator elements = fiber.iterator();
            while (elements.hasNext()) {
               Monomial m = (Monomial)elements.next();
               System.out.println(m);
            }
            System.exit(0);
         }
      } catch (java.io.FileNotFoundException ex) {
         System.err.println("Cannot find file: "+ex.getMessage());
      } catch (java.io.IOException ex) {
         ex.printStackTrace();
      }
      System.exit(1);
   }
   
}
